package org.xiaojinlong.regex.nfa;

import org.xiaojinlong.algo.ResizingArrayStack;
import org.xiaojinlong.algo.Stack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jin Long
 *         2016/2/2.
 */
public class SimpleRegex {

    // 给stateList中的State指定出状态
    private static void patch(List<State> stateList, State state) {
        for (State s : stateList) {
            if (s.c == State.SPLIT) {
                s.out2 = state;
            } else {
                s.out1 = state;
            }
        }
    }

    // 后缀表达式 -> NFA机器
    private static State postToNfa(char[] postfix) {
        Stack<Fragment> stack = new ResizingArrayStack<>();
        for (char c : postfix) {
            Fragment f1, f2;
            State s;
            List<State> outList;
            switch (c) {
                // 连接
                case '.':
                    f2 = stack.pop();
                    f1 = stack.pop();
                    patch(f1.out, f2.start);
                    stack.push(new Fragment(f1.start, f2.out));
                    break;
                // 或者
                case '|':
                    f2 = stack.pop();
                    f1 = stack.pop();
                    outList = new ArrayList<>();
                    outList.addAll(f1.out);
                    outList.addAll(f2.out);
                    stack.push(new Fragment(new State(State.SPLIT, f1.start, f2.start), outList));
                    break;
                // 可选
                case '?':
                    f1 = stack.pop();
                    s = new State(State.SPLIT, f1.start, null);
                    outList = new ArrayList<>();
                    outList.addAll(f1.out);
                    outList.add(s);
                    stack.push(new Fragment(s, outList));
                    break;
                // 0个或者多个
                case '*':
                    f1 = stack.pop();
                    s = new State(State.SPLIT, f1.start, null);
                    patch(f1.out, s);
                    outList = new ArrayList<>();
                    outList.add(s);
                    stack.push(new Fragment(s, outList));
                    break;
                // 1个或者多个
                case '+':
                    f1 = stack.pop();
                    s = new State(State.SPLIT, f1.start, null);
                    patch(f1.out, s);
                    outList = new ArrayList<>();
                    outList.add(s);
                    stack.push(new Fragment(f1.start, outList));
                    break;
                // 普通字符
                default:
                    s = new State(c, null, null);
                    outList = new ArrayList<>();
                    outList.add(s);
                    stack.push(new Fragment(s, outList));
                    break;
            }
        }

        Fragment f = stack.pop();
        if (!stack.isEmpty()) {
            return null;
        }
        patch(f.out, State.MATCH_STATE);

        return f.start;
    }

    private static int LIST_ID;
    private static List<State> startList(State start, List<State> l) {
        l.clear();
        LIST_ID++;
        addState(l, start);
        return l;
    }

    private static void addState(List<State> l, State s) {
        if (s == null || s.lastList == LIST_ID) {
            return;
        }
        s.lastList = LIST_ID;
        if (s.c == State.SPLIT) {
            addState(l, s.out1);
            addState(l, s.out2);
        } else {
            l.add(s);
        }
    }

    private static boolean isMatch(List<State> l) {
        for (State s : l) {
            if (s == State.MATCH_STATE) {
                return true;
            }
        }
        return false;
    }

    private static void step(List<State> clist, char c, List<State> nlist) {
        LIST_ID++;
        nlist.clear();
        for (State s : clist) {
            if (s.c == c) {
                addState(nlist, s.out1);
            }
        }
    }

    private static boolean match(State start, char[] chars) {
        List<State> tmp;
        List<State> current = startList(start, new ArrayList<>());
        List<State> next = new ArrayList<>();

        for (char c : chars) {
            step(current, c, next);
            tmp = current; current = next; next = tmp;
        }

        return isMatch(current);
    }

    public static void main(String[] args) {
        char[] postRe = "a+b?.cd.*.+e*|".toCharArray();
        char[] input = "aaabcdcd".toCharArray();
        State start = postToNfa(postRe);
        if (match(start, input)) {
            System.out.println(new String(input));
            System.out.println("match");
        }
    }
}
